package com.leetcode;

/**
 * @author yijy
 * @description
 * @create 2021/5/8 下午7:51
 **/
public class CoinSolution {

    public static void main(String[] args) {
        int[] f =  {2,5,7};
        System.out.println(new CoinSolution().coinChange(f, 27));
    }

    private int coinChange(int[] A, int m) {
        int[] f = new int[m+1];
        int n = A.length;

        f[0] = 0;

        for(int i=1; i<=m; i++){
            f[i] = Integer.MAX_VALUE;

            for(int j=0;j<n; j++){
                if(i>=A[j] && f[i-A[j]] != Integer.MAX_VALUE) {
                    f[i] = Math.min(f[i-A[j]] + 1, f[i]);
                }
            }
        }

        if(f[m] ==  Integer.MAX_VALUE){
            f[m] = -1;
        }

        return f[m];
    }
}
